// 2025/11/10
// 基本计算器

// 使用逆波兰表达式
class Solution {
    int cal(int num1, int num2, string op)
    {
        if (op == "+")
            return num1 + num2;
        else if (op == "-")
            return num1 - num2;
        else if (op == "*")
            return num1 * num2;
        else if (op == "/")
            return num1 / num2;
        else
            return 0;
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> opNum;
        for (auto& token : tokens)
        {
            if (token == "+" || token == "-" || token == "*" || token == "/")
            {
                int num2 = opNum.top(); opNum.pop();
                int num1 = opNum.top(); opNum.pop();
                opNum.emplace(cal(num1, num2, token));
            }
            else
            {
                opNum.emplace(stoi(token));
            }
        }
        return opNum.top();
    }

    vector<string> tokens;
    void exchange(string& s, int& pos)
    {
        stack<char> op;
        int count = 0, n = s.size();
        while (pos < n)
        {
            if ('0' <= s[pos] && s[pos] <= '9')
            {
                int tmp = pos;
                while (pos < n && '0' <= s[pos] && s[pos] <= '9')
                    pos++;
                if (pos != tmp)
                {
                    tokens.push_back(s.substr(tmp, pos - tmp));
                    if (++count == 2)
                    {
                        count = 1;
                        tokens.push_back(string(1, op.top()));
                        op.pop();
                    }
                }
            }
            else if (s[pos] == '+' || s[pos] == '-' || s[pos] == '*' || s[pos] == '/')
            {
                op.emplace(s[pos]);
                pos++;
            }
            else if (s[pos] == '(')
            {
                pos++;
                exchange(s, pos);
                if (++count == 2)
                {
                    count = 1;
                    tokens.push_back(string(1, op.top()));
                    op.pop();
                }
            }
            else if (s[pos] == ')')
            {
                pos++;
                return;
            }
        }
    }
public:
    int calculate(string s) {
        string goods;
        for (auto ch : s)
        {
            if (ch == ' ') continue;
            if (ch == '-' && (goods.empty() || goods.back() == '('))
                goods.push_back('0');
            goods.push_back(ch);
        }

        int pos = 0;
        exchange(goods, pos);
        return evalRPN(tokens);
    }
};

// 也没人告诉我这道题的操作符只包含'+'和'-'啊？
class Solution {
public:
    int calculate(string s) {
        int res = 0, sign = 1, n = s.size(); stack<int> st;
        for(int i = 0; i < n; i++)
        {
            if('0' <= s[i] && s[i] <= '9')
            {
                int num = 0;
                while(i < n && '0' <= s[i] && s[i] <= '9')
                {
                    num *= 10;
                    num += s[i] - '0';
                    i++;
                }
                i--; res += num * sign;
            }
            else if(s[i] == '+') sign = 1;
            else if(s[i] == '-') sign = -1;
            else if(s[i] == '(')
            {
                st.push(res); st.push(sign);
                res = 0; sign = 1;
            }
            else if(s[i] == ')')
            {
                res *= st.top(); st.pop();
                res += st.top(); st.pop();
            }
        }
        return res;
    }
};